package com.sheng.leetcode.year2022.month11.day09;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/11/09
 *<p>
 * 764. 最大加号标志<p>
 *<p>
 * 在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，<p>
 * 其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0<p>
 * 返回  grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。<p>
 * 一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，<p>
 * 以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。<p>
 * 注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。<p>
 *<p>
 * 示例 1：<p>
 * 输入: n = 5, mines = [[4, 2]]<p>
 * 输出: 2<p>
 * 解释: 在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。<p>
 *<p>
 * 示例 2：<p>
 * 输入: n = 1, mines = [[0, 0]]<p>
 * 输出: 0<p>
 * 解释: 没有加号标志，返回 0 。<p>
 *<p>
 * 提示：<p>
 * 1 <= n <= 500<p>
 * 1 <= mines.length <= 5000<p>
 * 0 <= xi, yi < n<p>
 * 每一对 (xi, yi) 都 不重复<p>
 */
public class LeetCode0764 {

    @Test
    public void test01() {
        int n = 5;
        int[][] mines = {{4, 2}};
//        int n = 1;
//        int[][] mines = {{0, 0}};
        System.out.println(new Solution().orderOfLargestPlusSign(n, mines));
    }
}
class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        // 将对应数组创建出来
        int[][] ints = new int[n][n];
        // 赋初始值
        for (int i = 0; i < n; i++) {
            Arrays.fill(ints[i], 1);
        }
        // 将 mines 中的值放入对应数组位置中
        for (int[] mine : mines) {
            ints[mine[0]][mine[1]] = 0;
        }
        // 返回值
        int ans = 0;
        // 每次循环的最大长度
        int max;
        for (int i = 0; i < n; i++) {
            // 过滤条件
            if (i < ans || i > n - 1 - ans) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                // 每次 j 循环过后再次进行判断
                if (i < ans || i > n - 1 - ans) {
                    break;
                }
                // 过滤
                if (j < ans || j > n - 1 - ans || ints[i][j] == 0) {
                    continue;
                }
                max = 0;
                // 当前位置坐标为1时
                while (i - max >= 0 && i + max < n && j - max >= 0 && j + max < n) {
                    // 判断是否满足上下左右都是1
                    if (ints[i][j - max] == 1 && ints[i][j + max] == 1 && ints[i - max][j] == 1 && ints[i + max][j] == 1) {
                        max++;
                    } else {
                        break;
                    }
                }
                // 赋值
                ans = Math.max(max, ans);
            }
        }
        return ans;
    }
}
